#pragma once
#include "stdio.h"
#include "string.h"
#include "iostream"
#include "vector"
#include "algorithm"
#include "unordered_map"
using namespace std;
/*HJJ QQ479287006
 *给你一个长度为 n 的数组 words ，该数组由 非空 字符串组成。

定义字符串 word 的 分数 等于以 word 作为 前缀 的 words[i] 的数目。

例如，如果 words = ["a", "ab", "abc", "cab"] ，那么 "ab" 的分数是 2 ，因为 "ab" 是 "ab" 和 "abc" 的一个前缀。
返回一个长度为 n 的数组 answer ，其中 answer[i] 是 words[i] 的每个非空前缀的分数 总和 。

注意：字符串视作它自身的一个前缀。



示例 1：

输入：words = ["abc","ab","bc","b"]
输出：[5,4,3,2]
解释：对应每个字符串的答案如下：
- "abc" 有 3 个前缀："a"、"ab" 和 "abc" 。
- 2 个字符串的前缀为 "a" ，2 个字符串的前缀为 "ab" ，1 个字符串的前缀为 "abc" 。
总计 answer[0] = 2 + 2 + 1 = 5 。
- "ab" 有 2 个前缀："a" 和 "ab" 。
- 2 个字符串的前缀为 "a" ，2 个字符串的前缀为 "ab" 。
总计 answer[1] = 2 + 2 = 4 。
- "bc" 有 2 个前缀："b" 和 "bc" 。
- 2 个字符串的前缀为 "b" ，1 个字符串的前缀为 "bc" 。
总计 answer[2] = 2 + 1 = 3 。
- "b" 有 1 个前缀："b"。
- 2 个字符串的前缀为 "b" 。
总计 answer[3] = 2 。
 * */

vector<string> getPre(string &word)
{
    vector<string> ret;

   string  s="";
    for (int i = 0; i <word.size() ; ++i) {
       s.push_back(word[i]);
        ret.push_back(s);
    }


    return ret;
}


 bool StartWith(const string& str, const string& prefix)
{
    if (strncmp(str.c_str(), prefix.c_str(), prefix.size()) == 0) {
        return true;
    }

    return false;
}


vector<int> sumPrefixScores(vector<string>& words) {
    vector<int> ret;

    unordered_map<string,int> pmap;
    for (int i = 0; i <words.size() ; ++i) {
        vector<string>  pres= getPre(words[i]);
        int count=0;
        for (int j = 0; j <pres.size() ; ++j) {
           auto iter= pmap.find(pres[j]);
           //如果缓存里面有直接push就行了
            if (iter!=pmap.end())
            {
                count+=iter->second;
                continue;
            } else{
                int temp=0;
                for (int k = 0; k <words.size() ; ++k) {
                    if (StartWith(words[k],pres[j]))
                    {
                        temp++;
                        count++;
                    }

                }
                pmap[pres[j]]=temp;
            }

        }
        ret.push_back(count);


    }





    return ret;


}